/*
 * Copyright 2012 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */
#ifndef SkOpSpan_DEFINED
#define SkOpSpan_DEFINED

#include "include/core/SkPoint.h"
#include "include/core/SkTypes.h"
#include "include/private/base/SkDebug.h"
#include "include/private/base/SkMath.h"
#include "src/pathops/SkPathOpsTypes.h"

class SkOpAngle;
class SkOpCoincidence;
class SkOpContour;
class SkOpSegment;
class SkOpSpan;
class SkOpSpanBase;

// subset of op span used by terminal span (when t is equal to one)
class SkOpPtT {
public:
    enum { kIsAlias = 1, kIsDuplicate = 1 };

    const SkOpPtT *active() const;

    // please keep in sync with debugAddOpp()
    void addOpp(SkOpPtT *opp, SkOpPtT *oppPrev)
    {
        SkOpPtT *oldNext = this->fNext;
        SkASSERT(this != opp);
        this->fNext = opp;
        SkASSERT(oppPrev != oldNext);
        oppPrev->fNext = oldNext;
    }

    bool alias() const;
    bool coincident() const
    {
        return fCoincident;
    }
    bool contains(const SkOpPtT *) const;
    bool contains(const SkOpSegment *, const SkPoint &) const;
    bool contains(const SkOpSegment *, double t) const;
    const SkOpPtT *contains(const SkOpSegment *) const;
    SkOpContour *contour() const;

    int debugID() const
    {
        return SkDEBUGRELEASE(fID, -1);
    }

    void debugAddOpp(const SkOpPtT *opp, const SkOpPtT *oppPrev) const;
    const SkOpAngle *debugAngle(int id) const;
    const SkOpCoincidence *debugCoincidence() const;
    bool debugContains(const SkOpPtT *) const;
    const SkOpPtT *debugContains(const SkOpSegment *check) const;
    SkOpContour *debugContour(int id) const;
    const SkOpPtT *debugEnder(const SkOpPtT *end) const;
    int debugLoopLimit(bool report) const;
    bool debugMatchID(int id) const;
    const SkOpPtT *debugOppPrev(const SkOpPtT *opp) const;
    const SkOpPtT *debugPtT(int id) const;
    void debugResetCoinT() const;
    const SkOpSegment *debugSegment(int id) const;
    void debugSetCoinT(int) const;
    const SkOpSpanBase *debugSpan(int id) const;
    void debugValidate() const;

    bool deleted() const
    {
        return fDeleted;
    }

    bool duplicate() const
    {
        return fDuplicatePt;
    }

    void dump() const; // available to testing only
    void dumpAll() const;
    void dumpBase() const;

    const SkOpPtT *find(const SkOpSegment *) const;
    SkOpGlobalState *globalState() const;
    void init(SkOpSpanBase *, double t, const SkPoint &, bool dup);

    void insert(SkOpPtT *span)
    {
        SkASSERT(span != this);
        span->fNext = fNext;
        fNext = span;
    }

    const SkOpPtT *next() const
    {
        return fNext;
    }

    SkOpPtT *next()
    {
        return fNext;
    }

    bool onEnd() const;

    // returns nullptr if this is already in the opp ptT loop
    SkOpPtT *oppPrev(const SkOpPtT *opp) const
    {
        // find the fOpp ptr to opp
        SkOpPtT *oppPrev = opp->fNext;
        if (oppPrev == this) {
            return nullptr;
        }
        while (oppPrev->fNext != opp) {
            oppPrev = oppPrev->fNext;
            if (oppPrev == this) {
                return nullptr;
            }
        }
        return oppPrev;
    }

    static bool Overlaps(const SkOpPtT *s1, const SkOpPtT *e1, const SkOpPtT *s2, const SkOpPtT *e2,
        const SkOpPtT **sOut, const SkOpPtT **eOut)
    {
        const SkOpPtT *start1 = s1->fT < e1->fT ? s1 : e1;
        const SkOpPtT *start2 = s2->fT < e2->fT ? s2 : e2;
        *sOut = between(s1->fT, start2->fT, e1->fT) ? start2 : between(s2->fT, start1->fT, e2->fT) ? start1 : nullptr;
        const SkOpPtT *end1 = s1->fT < e1->fT ? e1 : s1;
        const SkOpPtT *end2 = s2->fT < e2->fT ? e2 : s2;
        *eOut = between(s1->fT, end2->fT, e1->fT) ? end2 : between(s2->fT, end1->fT, e2->fT) ? end1 : nullptr;
        if (*sOut == *eOut) {
            SkOPOBJASSERT(s1, start1->fT >= end2->fT || start2->fT >= end1->fT);
            return false;
        }
        SkASSERT(!*sOut || *sOut != *eOut);
        return *sOut && *eOut;
    }

    bool ptAlreadySeen(const SkOpPtT *head) const;
    SkOpPtT *prev();

    const SkOpSegment *segment() const;
    SkOpSegment *segment();

    void setCoincident() const
    {
        SkOPASSERT(!fDeleted);
        fCoincident = true;
    }

    void setDeleted();

    void setSpan(const SkOpSpanBase *span)
    {
        fSpan = const_cast<SkOpSpanBase *>(span);
    }

    const SkOpSpanBase *span() const
    {
        return fSpan;
    }

    SkOpSpanBase *span()
    {
        return fSpan;
    }

    const SkOpPtT *starter(const SkOpPtT *end) const
    {
        return fT < end->fT ? this : end;
    }

    double fT;
    SkPoint fPt; // cache of point value at this t
protected:
    SkOpSpanBase *fSpan; // contains winding data
    SkOpPtT *fNext;      // intersection on opposite curve or alias on this curve
    bool fDeleted;       // set if removed from span list
    bool fDuplicatePt;   // set if identical pt is somewhere in the next loop
    // below mutable since referrer is otherwise always const
    mutable bool fCoincident; // set if at some point a coincident span pointed here
    SkDEBUGCODE(int fID);
};

class SkOpSpanBase {
public:
    enum class Collapsed {
        kNo,
        kYes,
        kError,
    };

    bool addOpp(SkOpSpanBase *opp);

    void bumpSpanAdds()
    {
        ++fSpanAdds;
    }

    bool chased() const
    {
        return fChased;
    }

    void checkForCollapsedCoincidence();

    const SkOpSpanBase *coinEnd() const
    {
        return fCoinEnd;
    }

    Collapsed collapsed(double s, double e) const;
    bool contains(const SkOpSpanBase *) const;
    const SkOpPtT *contains(const SkOpSegment *) const;

    bool containsCoinEnd(const SkOpSpanBase *coin) const
    {
        SkASSERT(this != coin);
        const SkOpSpanBase *next = this;
        while ((next = next->fCoinEnd) != this) {
            if (next == coin) {
                return true;
            }
        }
        return false;
    }

    bool containsCoinEnd(const SkOpSegment *) const;
    SkOpContour *contour() const;

    int debugBumpCount()
    {
        return SkDEBUGRELEASE(++fCount, -1);
    }

    int debugID() const
    {
        return SkDEBUGRELEASE(fID, -1);
    }

#if DEBUG_COIN
    void debugAddOpp(SkPathOpsDebug::GlitchLog *, const SkOpSpanBase *opp) const;
#endif
    bool debugAlignedEnd(double t, const SkPoint &pt) const;
    bool debugAlignedInner() const;
    const SkOpAngle *debugAngle(int id) const;
#if DEBUG_COIN
    void debugCheckForCollapsedCoincidence(SkPathOpsDebug::GlitchLog *) const;
#endif
    const SkOpCoincidence *debugCoincidence() const;
    bool debugCoinEndLoopCheck() const;
    SkOpContour *debugContour(int id) const;
#ifdef SK_DEBUG
    bool debugDeleted() const
    {
        return fDebugDeleted;
    }
#endif
#if DEBUG_COIN
    void debugInsertCoinEnd(SkPathOpsDebug::GlitchLog *, const SkOpSpanBase *) const;
    void debugMergeMatches(SkPathOpsDebug::GlitchLog *log, const SkOpSpanBase *opp) const;
#endif
    const SkOpPtT *debugPtT(int id) const;
    void debugResetCoinT() const;
    const SkOpSegment *debugSegment(int id) const;
    void debugSetCoinT(int) const;
#ifdef SK_DEBUG
    void debugSetDeleted()
    {
        fDebugDeleted = true;
    }
#endif
    const SkOpSpanBase *debugSpan(int id) const;
    const SkOpSpan *debugStarter(SkOpSpanBase const ** endPtr) const;
    SkOpGlobalState *globalState() const;
    void debugValidate() const;

    bool deleted() const
    {
        return fPtT.deleted();
    }

    void dump() const; // available to testing only
    void dumpCoin() const;
    void dumpAll() const;
    void dumpBase() const;
    void dumpHead() const;

    bool final() const
    {
        return fPtT.fT == 1;
    }

    SkOpAngle *fromAngle() const
    {
        return fFromAngle;
    }

    void initBase(SkOpSegment *parent, SkOpSpan *prev, double t, const SkPoint &pt);

    // Please keep this in sync with debugInsertCoinEnd()
    void insertCoinEnd(SkOpSpanBase *coin)
    {
        if (containsCoinEnd(coin)) {
            SkASSERT(coin->containsCoinEnd(this));
            return;
        }
        debugValidate();
        SkASSERT(this != coin);
        SkOpSpanBase *coinNext = coin->fCoinEnd;
        coin->fCoinEnd = this->fCoinEnd;
        this->fCoinEnd = coinNext;
        debugValidate();
    }

    void merge(SkOpSpan *span);
    bool mergeMatches(SkOpSpanBase *opp);

    const SkOpSpan *prev() const
    {
        return fPrev;
    }

    SkOpSpan *prev()
    {
        return fPrev;
    }

    const SkPoint &pt() const
    {
        return fPtT.fPt;
    }

    const SkOpPtT *ptT() const
    {
        return &fPtT;
    }

    SkOpPtT *ptT()
    {
        return &fPtT;
    }

    SkOpSegment *segment() const
    {
        return fSegment;
    }

    void setAligned()
    {
        fAligned = true;
    }

    void setChased(bool chased)
    {
        fChased = chased;
    }

    void setFromAngle(SkOpAngle *angle)
    {
        fFromAngle = angle;
    }

    void setPrev(SkOpSpan *prev)
    {
        fPrev = prev;
    }

    bool simple() const
    {
        fPtT.debugValidate();
        return fPtT.next()->next() == &fPtT;
    }

    int spanAddsCount() const
    {
        return fSpanAdds;
    }

    const SkOpSpan *starter(const SkOpSpanBase *end) const
    {
        const SkOpSpanBase *result = t() < end->t() ? this : end;
        return result->upCast();
    }

    SkOpSpan *starter(SkOpSpanBase *end)
    {
        SkASSERT(this->segment() == end->segment());
        SkOpSpanBase *result = t() < end->t() ? this : end;
        return result->upCast();
    }

    SkOpSpan *starter(SkOpSpanBase **endPtr)
    {
        SkOpSpanBase *end = *endPtr;
        SkASSERT(this->segment() == end->segment());
        SkOpSpanBase *result;
        if (t() < end->t()) {
            result = this;
        } else {
            result = end;
            *endPtr = this;
        }
        return result->upCast();
    }

    int step(const SkOpSpanBase *end) const
    {
        return t() < end->t() ? 1 : -1;
    }

    double t() const
    {
        return fPtT.fT;
    }

    void unaligned()
    {
        fAligned = false;
    }

    SkOpSpan *upCast()
    {
        SkASSERT(!final());
        return (SkOpSpan *)this;
    }

    const SkOpSpan *upCast() const
    {
        SkOPASSERT(!final());
        return (const SkOpSpan *)this;
    }

    SkOpSpan *upCastable()
    {
        return final() ? nullptr : upCast();
    }

    const SkOpSpan *upCastable() const
    {
        return final() ? nullptr : upCast();
    }

private:
    void alignInner();

protected:                  // no direct access to internals to avoid treating a span base as a span
    SkOpPtT fPtT;           // list of points and t values associated with the start of this span
    SkOpSegment *fSegment;  // segment that contains this span
    SkOpSpanBase *fCoinEnd; // linked list of coincident spans that end here (may point to itself)
    SkOpAngle *fFromAngle;  // points to next angle from span start to end
    SkOpSpan *fPrev;        // previous intersection point
    int fSpanAdds;          // number of times intersections have been added to span
    bool fAligned;
    bool fChased;            // set after span has been added to chase array
    SkDEBUGCODE(int fCount); // number of pt/t pairs added
    SkDEBUGCODE(int fID);
    SkDEBUGCODE(bool fDebugDeleted); // set when span was merged with another span
};

class SkOpSpan : public SkOpSpanBase {
public:
    bool alreadyAdded() const
    {
        if (fAlreadyAdded) {
            return true;
        }
        return false;
    }

    bool clearCoincident()
    {
        SkASSERT(!final());
        if (fCoincident == this) {
            return false;
        }
        fCoincident = this;
        return true;
    }

    int computeWindSum();
    bool containsCoincidence(const SkOpSegment *) const;

    bool containsCoincidence(const SkOpSpan *coin) const
    {
        SkASSERT(this != coin);
        const SkOpSpan *next = this;
        while ((next = next->fCoincident) != this) {
            if (next == coin) {
                return true;
            }
        }
        return false;
    }

    bool debugCoinLoopCheck() const;
#if DEBUG_COIN
    void debugInsertCoincidence(SkPathOpsDebug::GlitchLog *, const SkOpSpan *) const;
    void debugInsertCoincidence(SkPathOpsDebug::GlitchLog *, const SkOpSegment *, bool flipped, bool ordered) const;
#endif
    void dumpCoin() const;
    bool dumpSpan() const;

    bool done() const
    {
        SkASSERT(!final());
        return fDone;
    }

    void init(SkOpSegment *parent, SkOpSpan *prev, double t, const SkPoint &pt);
    bool insertCoincidence(const SkOpSegment *, bool flipped, bool ordered);

    // Please keep this in sync with debugInsertCoincidence()
    void insertCoincidence(SkOpSpan *coin)
    {
        if (containsCoincidence(coin)) {
            SkASSERT(coin->containsCoincidence(this));
            return;
        }
        debugValidate();
        SkASSERT(this != coin);
        SkOpSpan *coinNext = coin->fCoincident;
        coin->fCoincident = this->fCoincident;
        this->fCoincident = coinNext;
        debugValidate();
    }

    bool isCanceled() const
    {
        SkASSERT(!final());
        return fWindValue == 0 && fOppValue == 0;
    }

    bool isCoincident() const
    {
        SkASSERT(!final());
        return fCoincident != this;
    }

    void markAdded()
    {
        fAlreadyAdded = true;
    }

    SkOpSpanBase *next() const
    {
        SkASSERT(!final());
        return fNext;
    }

    int oppSum() const
    {
        SkASSERT(!final());
        return fOppSum;
    }

    int oppValue() const
    {
        SkASSERT(!final());
        return fOppValue;
    }

    void release(const SkOpPtT *);

    SkOpPtT *setCoinStart(SkOpSpan *oldCoinStart, SkOpSegment *oppSegment);

    void setDone(bool done)
    {
        SkASSERT(!final());
        fDone = done;
    }

    void setNext(SkOpSpanBase *nextT)
    {
        SkASSERT(!final());
        fNext = nextT;
    }

    void setOppSum(int oppSum);

    void setOppValue(int oppValue)
    {
        SkASSERT(!final());
        SkASSERT(fOppSum == SK_MinS32);
        SkOPASSERT(!oppValue || !fDone);
        fOppValue = oppValue;
    }

    void setToAngle(SkOpAngle *angle)
    {
        SkASSERT(!final());
        fToAngle = angle;
    }

    void setWindSum(int windSum);

    void setWindValue(int windValue)
    {
        SkASSERT(!final());
        SkASSERT(windValue >= 0);
        SkASSERT(fWindSum == SK_MinS32);
        SkOPASSERT(!windValue || !fDone);
        fWindValue = windValue;
    }

    bool sortableTop(SkOpContour *);

    SkOpAngle *toAngle() const
    {
        SkASSERT(!final());
        return fToAngle;
    }

    int windSum() const
    {
        SkASSERT(!final());
        return fWindSum;
    }

    int windValue() const
    {
        SkOPASSERT(!final());
        return fWindValue;
    }

private:                   // no direct access to internals to avoid treating a span base as a span
    SkOpSpan *fCoincident; // linked list of spans coincident with this one (may point to itself)
    SkOpAngle *fToAngle;   // points to next angle from span start to end
    SkOpSpanBase *fNext;   // next intersection point
    int fWindSum;          // accumulated from contours surrounding this one.
    int fOppSum;           // for binary operators: the opposite winding sum
    int fWindValue;        // 0 == canceled; 1 == normal; >1 == coincident
    int fOppValue;         // normally 0 -- when binary coincident edges combine, opp value goes here
    int fTopTTry;          // specifies direction and t value to try next
    bool fDone;            // if set, this span to next higher T has been processed
    bool fAlreadyAdded;
};

#endif
